1. Field of the Invention
This invention relates to numerical sorting logic and more particularly to multipass numerical sorting logic where the input list is divided into groups which are individually sorted and then merged to form a single sorted output list.
2. Description of the Prior Art
Heretofore, numerical sorting was done primarily by relatively slow software programs. The limited sorting hardware that was available is based on a cumbersome comparison technique which sometimes required more comparator elements than words in the input list. In some instances the circuitry required increased geometrically as the number N of elements in the input list expanded. Further, these prior art hardware and software sorters are not fast enough for CRT display applications. The following references teach prior art sorting:
(A) K. E. Batcher: Sorting Networks and Their Applications (AFIPS Proc., Vol. 32, 1968, p. 307); PA1 (B) D. G. O'Connor et al: Sorting System with N-Line Sorting Switch PA1 (C) Knuth: Art of Computer Programming, Vol. 3, Sorting and Searching, para. 5.3.4, Networks for Sorting; and PA1 (D) W. H. Kautz: Cellular Logic-in-Memory Arrays (IEEE Transactions on Computers, August 1969, page 719).